package org.example.sword2offer.primary;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: lynn
 * @Descript: 二叉搜索树的后序遍历序列
 * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。
 * 假设输入的数组的任意两个数字都互不相同。
 * @date: 2021/3/11 22:47
 * @version: 1.0
 */
public class Q23_VerifySquenceOfBST_H {
    public static void main(String[] args) {
        int[] array={4,8,6,12,16,14,10};
        System.out.println(
                Boolean.toString(
                        VerifySquenceOfBST(array))
        );
    }
    public static boolean VerifySquenceOfBST(int [] sequence){
        if(sequence == null || sequence.length == 0) {
            return false;
        }
        else if(sequence.length == 1) {
            return true;
        }

        return JudgePostOrder(sequence, 0, sequence.length - 1);

    }


    /**  int[] array={4,8,6,12,16,14,10};
     * 后续遍历得到的序列中最后一个元素一定是树的根节点的值。数组中前面的数字可以分为两部分：
     * 左子树的值序列和右子树的值序列。左子树值都小于根节点值，右子树值都大于根节点值。
     * 确定了左子树值和右子树值的序列，还是按上面的方法确定对应的子树的结构，这是一个递归的过程。
     * 如果递归过程中发现其右子序列中有值小于根值，那么这不是一个后序序列。
     */
    public static boolean JudgePostOrder(int[] sequence, int start, int end) {
        if (start >= end) {
            return true;
        }
        //找出前子序列
        int i = start;
        while (i <= end && sequence[i] < sequence[end]) {
            i++;
        }
        for (int j = i; j <= end; j++) {
            if (sequence[j] < sequence[end]) {
                return false;
            }
        }
        return JudgePostOrder(sequence, start, i - 1) && JudgePostOrder(sequence, i, end - 1);
    }
}
